import java.util.ArrayList;
import java.util.List;

public class Test {


    //翻转对
    //降序版本
    int[] tmp;
    public int reversePairs3(int[] nums){
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(nums,0,n-1);
    }
    public int mergeSort(int[] nums,int left,int right){
        if(left>= right) return 0;
        int ret=0;
        int mid = (left+right)/2;
        ret+=mergeSort(nums,left,mid);
        ret+=mergeSort(nums,mid+1,right);
        int cur1 = left,cur2 = mid+1,i=left;
        while(cur1<=mid){
            while(cur2<= right && nums[cur2]>= nums[cur1]/2.0) cur2++;
            if (cur2>right) break;
            ret+= right-cur2+1;
            cur1++;
        }

        cur1 = left;
        cur2 = mid+1;
        while(cur1<=mid && cur2<=right) tmp[i++] = nums[cur1] <= nums[cur2] ?nums[cur2++]:nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        for(int j = left; j <= right; j++)
            nums[j] = tmp[j];
        return ret;
    }
    //升序版本
    int[] tmpp;
    public int reversePairs5(int[] nums){
        int n = nums.length;
        tmpp = new int[n];
        return mergeSort6(nums,0,n-1);
    }
    public int mergeSort6(int[] nums,int left,int right){
        if(left >= right) return 0;
        int ret = 0;
        // 1. 根据中间元素，将区间分成两部分
        int mid = (left + right) / 2;
        // [left, mid] [mid + 1, right]
        // 2. 求出左右两个区间的翻转对
        ret += mergeSort6(nums, left, mid);
        ret += mergeSort6(nums, mid + 1, right);
        // 3. 处理⼀左⼀右 - 先计算翻转对
        int cur1 = left, cur2 = mid + 1, i = left;
        // 升序版本
        while(cur2 <= right)
        {
            while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;
            if(cur1 > mid)
                break;
            ret += mid - cur1 + 1;
            cur2++;
        }
        // 4. 合并两个有序数组 - 升序
         cur1 = left; cur2 = mid + 1;
         while(cur1 <= mid && cur2 <= right)
             tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
         while(cur1 <= mid) tmp[i++] = nums[cur1++];
         while(cur2 <= right) tmp[i++] = nums[cur2++];

         for(int j = left; j <= right; j++)
             nums[j] = tmp[j];

         return ret;
         }
    }




    //计算右侧小于当前元素的个数
    int[] ret;//统计返回的数组
    int[] index;//记录原数组的下标
    int[] tmpIndex;//记录修改后的下标
    int[] tmpNums;//记录修改后的nums数组列

    public List<Integer> countSmaller(int[] nums){
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        tmpIndex = new int[n];
        tmpNums = new int[n];

        for (int i = 0; i < n; i++) {
            index[i] = i;
        }

        mergeSort4(nums,0,n-1);
        List<Integer> l = new ArrayList<Integer>();
        for (int x : ret) {
            l.add(x);
        }
        return l;
    }
    public void mergeSort4(int[] nums,int left,int right){
        if (left>= right) return;

        int mid = (left+right)/2;

        mergeSort4(nums,left,mid);
        mergeSort4(nums,mid+1,right);

        int cur1 = left, cur2 = mid+1, i=0;
        while(cur1<=mid && cur2<=right){//降序
            if (nums[cur1] <= nums[cur2]){
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }else{
                ret[index[cur1]] += right-cur2+1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
        }
        while(cur1<=mid){
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = nums[cur1++];
        }
        while(cur2<=right){
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }
        for (int j = left; j <= right; j++) {
            nums[j] = tmpNums[j-left];
            index[j] = tmpIndex[j-left];
        }
    }





    //数组中的逆序对
    //降序版本
    int[] tmp3;
    public int reversePairs2(int[] nums){
        int n = nums.length;
        tmp3 = new int[n];
        return mergeSort3(nums,0,n-1);
    }
    public int mergeSort3(int[]nums,int left,int right){
        if (left>right) return 0;

        int ret = 0;
        int mid = (left+right)/2;
        ret+=mergeSort3(nums,left,mid);
        ret+=mergeSort3(nums,mid+1,right);

        int cur1 = left,cur2 = mid+1,i = 0;
        while(cur1<=mid && cur2<=right){
            if (nums[cur1] <= nums[cur2]){
                tmp3[i++] = nums[cur2++];
            }else{
                ret+= right-cur2+1;
                tmp3[i++] = nums[cur1++];
            }
        }

        while(cur1<=mid){
            tmp3[i++] = nums[cur1++];
        }
        while(cur2<=right){
            tmp3[i++] = nums[cur2++];
        }
        for (int j = left; j < right; j++) {
            nums[i] = tmp3[j-left];
        }
        return ret;
    }
    //升序版本
    int[] tmp2;
    public int reversePairs(int[] nums){
        int n = nums.length;
        tmp2 = new int[n];
        return mergeSort2(nums,0,n-1);
    }
    public int mergeSort2(int[] nums,int left,int right){
        if (left > right) return 0;

        int ret = 0;

        int mid = (left+right)/2;

        ret+=mergeSort2(nums,left,mid);
        ret+=mergeSort2(nums,mid+1,right);

        int cur1 = left, cur2 = mid+1,i = 0;
        while(cur1<=mid && cur2<=right){
            if (nums[cur1] <= nums[cur2]){
                tmp2[i++] = nums[cur1++];
            }else{
                ret+=(mid-left+1);
                tmp2[i++] = nums[cur2++];
            }
        }

        while(cur1<=mid){
            tmp2[i++] = nums[cur1++];
        }
        while (cur2<= right){
            tmp2[i++] = nums[cur2++];
        }

        for (int j = left; j < right; j++) {
            nums[j] = tmp2[j-left];
        }
        return ret;
    }



    //排序数组
    int[] tmp1;
    public int[] sortArray(int[] nums){
        tmp1 = new int[nums.length];
        mergeSort1(nums,0,nums.length);
        return nums;
    }
    public void mergeSort1(int[] nums,int left, int right){
        if (left>right) return;

        int mid = (left+right)/2;

        mergeSort1(nums,left,mid);
        mergeSort1(nums,mid+1,right);

        int cur1 = left,cur2 = mid+1, i = 0;
        while (cur1<=mid && cur2<=right){
            tmp1[i++] = nums[cur1] <= nums[cur2] ? nums[cur1] : nums[cur2];
        }

        while(cur1 <= mid){
            tmp1[i++] = nums[cur1++];
        }

        while (cur2 <= right){
            tmp1[i++] = nums[cur2++];
        }

        for (int j =left;j <= right;j++) {
            nums[j] = tmp1[j-left];
        }
    }
}
